/*
 * Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. 
You may not modify the values in the list, only nodes itself can be changed.
 */
package com.xinpan.exercise;

public class SwapNodesInPairs {
    public ListNode swapPairs(ListNode head) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(head == null)
            return null;
        
        
        ListNode newH = new ListNode(-1);
        newH.next = head;
        
        ListNode pre = head;
        ListNode cur = head.next;
        if(cur == null)
            return pre;
        ListNode fHead = cur;
            
        while(cur != null)
        {
            ListNode next = cur.next;
            pre.next = next;
            cur.next = pre;
            newH.next = cur;
            
            newH = pre;
            pre = newH.next;
            if(pre == null)
                break;
            cur = pre.next;
        }
        
        return fHead;
    }
}
